/**
 * 55. 跳跃游戏
 * https://leetcode-cn.com/problems/jump-game/
 */
public class Solutions_55 {
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};  // output: true
//        int[] nums = {3, 2, 1, 0, 4};  // output: false
//        int[] nums = {0, 1};  // output: false
//        int[] nums = {0};  // output: true
//        int[] nums = {1, 1, 1, 0};  // output: true
//        int[] nums = {2, 0, 1, 0, 1};  // output: false

        boolean result = canJump3(nums);
        System.out.println(result);
    }

    /**
     * 解法三：倒序遍历（1ms）
     */
    public static boolean canJump(int[] nums) {
        // 只有一位元素的情况时，就是在最后一个位置上
        if (nums == null || nums.length <= 1) {
            return true;
        }
        // 若 nums 长度大于 1，那么想到到达最后一个位置，最少需要跳跃一个单位距离
        int distance = 1;
        // 倒数第二位开始遍历
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] >= distance) {
                // 最少需要跳跃一个单位距离到索引 i 上
                distance = 1;
            } else {
                // i 索引上不能够跳跃到后面的索引上，需要索引 i 前面的索引来进行跳跃
                // 距离累积
                distance ++;
            }
        }
        // 最终，最少需要跳跃的距离为 distance，若 nums[0] 上的元素满足，则为 true
        return nums[0] >= distance;
    }

    /**
     * 解法二：正序遍历（2ms）
     */
    public static boolean canJump3(int[] nums) {
        int len = nums.length;
        // 记录能够走到的最远的索引
        int energy = 0;
        for (int i = 0; i < len; i++) {
            if (i <= energy) {
                // 可以继续往后走，计算能够走到的最远的索引
                // 最远的距离 = 当前索引 i + 能够再往后走 nums[i] 个单位
                energy = Math.max(energy, i + nums[i]);
            } else {
                // “能量”不够，将无法走到索引 i 上
                break;
            }
            if (energy >= len - 1) {
                // 拥有的“能量”一定能够到达最后一个位置
                return true;
            }
        }
        return false;
    }

    /**
     * 解法一：正序遍历（2ms）
     */
    public static boolean canJump2(int[] nums) {
        // 只有一位元素的情况时，就是在最后一个位置上
        if (nums == null || nums.length <= 1) {
            return true;
        }
        // 初始时，拥有 have 个“能量”
        int have = nums[0];
        int i = 0;
        for ( ; i < nums.length; i++) {
            if (have == 0) {
                // 无法再进行跳跃的情况
                break;
            }
            // 比较当前索引上能够获得的“能量”与已有的能量减 1，二者取最大值
            have = Math.max(nums[i], have - 1);
            if (i + have >= nums.length - 1) {
                // 提前结束循环：当前的“能量”一定能够到达最后一个位置上时，直接跳跃到最后一个位置
                return true;
            }
        }
        return false;
    }
}
